import java.lang.reflect.Array;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2024-02-01
 * Time: 23:15
 * <p>
 * https://www.nowcoder.com/share/jump/7745334641706803022291
 */


public class BM96 {
    public int minmumNumberOfHost(int n, int[][] startEnd) {
        Arrays.sort(startEnd, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(Integer.MIN_VALUE);
        for (int i = 0; i < n; i++) {
            // 如果当前结束时间小于等于下一轮的开始时间，不需要新的主持人
            if (pq.peek() <= startEnd[i][0]) {
                pq.poll();
            }
            // 添加新的开始结束时间
            pq.offer(startEnd[i][1]);
        }
        // 剩余的节点数，即是主持人数
        return pq.size();
    }
}


class BM96_1 {

    public int minmumNumberOfHost(int n, int[][] startEnd) {
        // 使用数组存放开始时间和结束时间
        int[] start = new int[n];
        int[] end = new int[n];
        // 记录时间
        for (int i = 0; i < n; i++) {
            start[i] = startEnd[i][0];
            end[i] = startEnd[i][1];
        }
        // 排列时间
        Arrays.sort(start);
        Arrays.sort(end);
        int j = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            // 新开始的节目大于上一轮节目的结束时间，主持人不变
            if (start[i] >= end[j]) {
                j++;
            } else {
                res++;
            }
        }
        return res;
    }
}